package com.wtgroup.demo.leetcode.q053_最大子序和;

/**
 * @author 60906
 * @date 2021/5/11 12:25
 */
public class Q053 {

    /**贪心
     *
     * 遇到新数字时, 旧的子序加上新数 <= 新数, 那么旧的子序丢弃, 只用新数作为新的子序.
     * 效率: 100%;
     *
     * 实际是 LC 动态规划
     * */
    private class Solution_MyGreed {
        public int maxSubArray(int[] nums) {
            int n = nums.length;
            if (n==0) {
                return 0;
            }
            // 上一次子序和
            int lastSubArrSum = nums[0];
            int ans = lastSubArrSum;
            for (int i = 1; i < n; i++) {
                // 合伙和单干取大者
                lastSubArrSum = Math.max(lastSubArrSum + nums[i], nums[i]);
                ans = Math.max(ans, lastSubArrSum);
            }

            return ans;
        }
    }

    /**
     * LC 方法2 分治
     * 用到了线段树相关思想.
     */

}
